<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Hard
  </div>
  <div>
   <h1 class="question_title">
    10. Regular Expression Matching
   </h1>
   <p>
    Given an input string (
    <code>
     s
    </code>
    ) and a pattern (
    <code>
     p
    </code>
    ), implement regular expression matching with support for
    <code>
     '.'
    </code>
    and
    <code>
     '*'
    </code>
    .
   </p>
   <pre>
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
</pre>
   <p>
    The matching should cover the
    <strong>
     entire
    </strong>
    input string (not partial).
   </p>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ul>
    <li>
     <code>
      s
     </code>
     &nbsp;could be empty and contains only lowercase letters
     <code>
      a-z
     </code>
     .
    </li>
    <li>
     <code>
      p
     </code>
     could be empty and contains only lowercase letters
     <code>
      a-z
     </code>
     , and characters like&nbsp;
     <code>
      .
     </code>
     &nbsp;or&nbsp;
     <code>
      *
     </code>
     .
    </li>
   </ul>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input:</strong>
s = "aa"
p = "a"
<strong>Output:</strong> false
<strong>Explanation:</strong> "a" does not match the entire string "aa".
</pre>
   <p>
    <strong>
     Example 2:
    </strong>
   </p>
   <pre>
<strong>Input:</strong>
s = "aa"
p = "a*"
<strong>Output:</strong> true
<strong>Explanation:</strong>&nbsp;'*' means zero or more of the precedeng&nbsp;element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
</pre>
   <p>
    <strong>
     Example 3:
    </strong>
   </p>
   <pre>
<strong>Input:</strong>
s = "ab"
p = ".*"
<strong>Output:</strong> true
<strong>Explanation:</strong>&nbsp;".*" means "zero or more (*) of any character (.)".
</pre>
   <p>
    <strong>
     Example 4:
    </strong>
   </p>
   <pre>
<strong>Input:</strong>
s = "aab"
p = "c*a*b"
<strong>Output:</strong> true
<strong>Explanation:</strong>&nbsp;c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
</pre>
   <p>
    <strong>
     Example 5:
    </strong>
   </p>
   <pre>
<strong>Input:</strong>
s = "mississippi"
p = "mis*is*p*."
<strong>Output:</strong> false
</pre>
  </div>
  <div>
   <h1 class="question_title">
    10. 正则表达式匹配
   </h1>
   <p>
    给定一个字符串&nbsp;(
    <code>
     s
    </code>
    ) 和一个字符模式&nbsp;(
    <code>
     p
    </code>
    )。实现支持
    <code>
     '.'
    </code>
    &nbsp;和&nbsp;
    <code>
     '*'
    </code>
    &nbsp;的正则表达式匹配。
   </p>
   <pre>'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。
</pre>
   <p>
    匹配应该覆盖
    <strong>
     整个
    </strong>
    字符串&nbsp;(
    <code>
     s
    </code>
    ) ，而不是部分字符串。
   </p>
   <p>
    <strong>
     说明:
    </strong>
   </p>
   <ul>
    <li>
     <code>
      s
     </code>
     &nbsp;可能为空，且只包含从&nbsp;
     <code>
      a-z
     </code>
     &nbsp;的小写字母。
    </li>
    <li>
     <code>
      p
     </code>
     &nbsp;可能为空，且只包含从&nbsp;
     <code>
      a-z
     </code>
     &nbsp;的小写字母，以及字符&nbsp;
     <code>
      .
     </code>
     &nbsp;和&nbsp;
     <code>
      *
     </code>
     。
    </li>
   </ul>
   <p>
    <strong>
     示例 1:
    </strong>
   </p>
   <pre><strong>输入:</strong>
s = "aa"
p = "a"
<strong>输出:</strong> false
<strong>解释:</strong> "a" 无法匹配 "aa" 整个字符串。
</pre>
   <p>
    <strong>
     示例 2:
    </strong>
   </p>
   <pre><strong>输入:</strong>
s = "aa"
p = "a*"
<strong>输出:</strong> true
<strong>解释:</strong>&nbsp;'*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
</pre>
   <p>
    <strong>
     示例&nbsp;3:
    </strong>
   </p>
   <pre><strong>输入:</strong>
s = "ab"
p = ".*"
<strong>输出:</strong> true
<strong>解释:</strong>&nbsp;".*" 表示可匹配零个或多个('*')任意字符('.')。
</pre>
   <p>
    <strong>
     示例 4:
    </strong>
   </p>
   <pre><strong>输入:</strong>
s = "aab"
p = "c*a*b"
<strong>输出:</strong> true
<strong>解释:</strong>&nbsp;'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。
</pre>
   <p>
    <strong>
     示例 5:
    </strong>
   </p>
   <pre><strong>输入:</strong>
s = "mississippi"
p = "mis*is*p*."
<strong>输出:</strong> false</pre>
  </div>
 </body>
</html>